/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2019年4月23日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson3.tree.binarytree;

import java.util.Arrays;

/**
 * @Type HeapSort
 * @Desc
 * @author 52489
 * @date 2019年4月23日
 * @Version V1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[] { 9, 6, 8, 7, 0, 1, 10, 4, 2 };
        // 开始位置是最后一个非叶子节点，既最后一个节点的父节点

        int start = (arr.length - 1) / 2;
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void maxHeap(int[] arr, int size, int index) {
        // 左子节点
        int leftNode = 2 * index + 1;
        // 右子节点
        int rightNode = 2 * index + 2;
        int max = index;
        // 和两个子节点分别对比，最大的两个节点
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }

        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }
        // 交换位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            maxHeap(arr, size, max);
        }
    }
}
